#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    private:
    vector<vector<int>> ret;

    public:
    void dfs(vector<int>& candidates, int target, vector<int>& combin, int index){
        if(index == candidates.size()){
            return;
        }
        if(target == 0){
            ret.push_back(combin);
            return;
        }

        dfs(candidates, target, combin, index+1);
        if(target - candidates[index] >= 0){
            combin.push_back(candidates[index]);
            dfs(candidates, target-candidates[index], combin, index);
            combin.pop_back();
        }
    }

    vector<vector<int>> ans1(vector<int>& candidates, int target){
        vector<int> combin;

        dfs(candidates, target, combin, 0);
        return ret;
    }

    void back(vector<int>& candidates, int target,int index, vector<int>& combin){
        if(target < 0){
            return;
        }
        if(target == 0){
            ret.push_back(combin);
        }

        for(int i = 0; i <= index; i++){
            combin.push_back(candidates[i]);
            back(candidates, target-candidates[i], i, combin);
            combin.pop_back();
        }
    }

    vector<vector<int>> ans2(vector<int>& candidates, int target){
        vector<int> combin;
        back(candidates, target, candidates.size()-1, combin);

        return ret;
    }
};

void test1(){
    Solution s;
    vector<int> candidates = {2,3,6,7};
    int target = 7;
    // vector<vector<int>> ret = s.ans1(candidates, target);
    vector<vector<int>> ret = s.ans2(candidates, target);
    for(int i = 0; i != ret.size(); i++){
        for(int j = 0; j != ret[i].size()-1; j++){
            cout << ret[i][j] << " " << ends;
        }
        cout << ret[i][ret[i].size()-1] << endl;
    }
}

void test2(){
    Solution s;
    vector<int> candidates = {2,3,5};
    int target = 8;
    vector<vector<int>> ret = s.ans1(candidates, target);
    for(int i = 0; i != ret.size(); i++){
        for(int j = 0; j != ret[i].size()-1; j++){
            cout << ret[i][j] << " " << ends;
        }
        cout << ret[i][ret[i].size()-1] << endl;
    }
}

int main(void){
    test1();
    test2();

    return 0;
}